Algorytmy danych geoprzestrzennych

Wprowadzenie

Krzysztof Dyba

Informacje o zajęciach

Wykłady

  • liczba godzin: 15
  • zaliczenie: test

Ćwiczenia

  • liczba godzin: 30
  • część praktyczna w PyQGIS
  • zaliczenie: projekt końcowy + zadania na zajęciach




Kontakt:

Źródła wiedzy

Czym jest algorytm?

Algorytm

Algorytm to zestaw precyzyjnie zdefiniowanych instrukcji krok po kroku służących do rozwiązania konkretnego problemu lub wykonania zadania w skończonym czasie.

Jest to jednoznaczna sekwencja operacji, która wykorzystuje dane wejściowe, przetwarza je zgodnie z określonymi zasadami i generuje dane wyjściowe.

Cechy algorytmu

  • Jednoznaczność – każdy krok algorytmu musi być precyzyjnie i jednoznacznie zdefiniowany bez miejsca na otwarte interpretacje.
  • Skończoność – algorytm musi zakończyć działanie po skończonej liczbie kroków, tj. nie może działać w nieskończoność.
  • Efektywność – każdy krok algorytmu musi być wykonywalny i osiągalny przy użyciu dostępnych zasobów.
  • Poprawność – algorytm powinien generować poprawne dane wyjściowe (dla poprawnych danych wejściowych).

Przykłady algorytmów

Przepis kuchenny to instrukcja w jaki sposób przygotować składniki (dane wejściowe), aby otrzymać potrawę (dane wyjściowe).

  • Algorytmy sortowania (np. bąbelkowe, pozycyjne).
  • Algorytmy wyszukiwania (np. liniowe, binarne).
  • Algorytmy szyfrowania (np. algorytm Huffmana).
  • Algorytmy uczenia maszynowego.
  • …i wiele innych!

Schemat blokowy

flowchart TD
    A[Start] --> B{PUNKT DECYZYJNY}
    B -->|Tak| C[AKCJA 1]
    B -->|Nie| D[AKCJA 2]
    C --> E[Koniec]
    D --> E

Prostokąt reprezentuje etap procesu.

Romb reprezentuje punkt decyzyjny, który rozgałęzia przepływ na podstawie warunków TAK/NIE lub PRAWDA/FAŁSZ.

Schemat blokowy to wizualna reprezentacja procesu, która ilustruje sekwencję kroków, decyzji i działań podejmowanych w celu osiągnięcia określonego celu.

W przeciwieństwie do algorytmu, cechuje się uproszczoną formą, przez co jest łatwiejszy w odbiorze.

https://mermaid.js.org/

Przykład

Szukanie wartości maksymalnej w zbiorze

Przykład

Dane wejściowe: Lista liczb.

Dane wyjściowe: Największa liczba z listy.

Kroki:

  1. Ustaw pierwszą liczbę z listy jako największą.

  2. Dla każdej liczby na liście:

    Jeśli bieżąca liczba jest większa od największej, to ustaw ją na bieżącą.

  3. Zwróć największą liczbę.

Przykład – schemat blokowy

flowchart LR
    A[Start] --> B[Ustaw pierwszy element jako maks]
    B --> C[Dla każdego elementu z listy]
    C --> D{Czy bieżący element jest większy od maks?}
    D -- Tak --> E[Ustaw nowe maksimum]
    D -- Nie --> F[Sprawdź kolejny element]
    E --> F
    F --> G{Czy są kolejne elementy do sprawdzenia?}
    G -- Tak --> C
    G -- Nie --> H[Zwróć maks]
    H --> I[Koniec]


flowchart LR
    A[Start] --> B[Ustaw pierwszy element jako maks]
    B --> C[Dla każdego elementu z listy]
    C --> D{Czy bieżący element jest większy od maks?}
    D -- Tak --> E[Ustaw nowe maksimum]
    D -- Nie --> F[Sprawdź kolejny element]
    E --> F
    F --> G{Czy są kolejne elementy do sprawdzenia?}
    G -- Tak --> C
    G -- Nie --> H[Zwróć maks]
    H --> I[Koniec]

Przykład – pseudokod

Pseudokod – uproszczony sposób opisywania logiki algorytmu bez użycia ścisłej składni określonego języka programowania. Traktowany jest jako szkic kodu, zatem nie może zostać uruchomiony na komputerach.

ALGORYTM ZnajdzMaks(lista)
  maks = lista[1]
  FOR kazdego elementu IN lista:
    IF element > maks THEN
      maks = element
  RETURN maks

Przykład – implementacja

Python

liczby = [1, 5, 2, 8, 3, 9, 4, 7, 6]
maks = liczby[0]

for liczba in liczby:
  if liczba > maks:
    maks = liczba
print(maks)
#> 9

R

liczby = c(1, 5, 2, 8, 3, 9, 4, 7, 6)
maks = liczby[1]

for (liczba in liczby) {
  if (liczba > maks) {
    maks = liczba
  }
}
print(maks)
#> 9


Jakie są różnice między tymi dwoma blokami kodu?

Złożoność algorytmu

Złożoność algorytmu to miara wzrostu zużycia zasobów przez algorytm wraz ze wzrostem wielkości danych wejściowych.

Główne typy:

  • Złożoność czasowa.
  • Złożoność pamięci.

Do opisania złożoności algorytmu powszechnie stosowana jest notacja dużego \(O\), opisująca najgorszy scenariusz działania.

Złożoność algorytmu

Złożoność algorytmu

Notacja Funkcja Opis Przykład
\(O(1)\) Stała Czas wykonania nie zależy od wielkości danych wejściowych Dostęp do określonego elementu tablicy poprzez jego indeks
\(O(\log n)\) Logarytmiczna Zazwyczaj algorytm dzieli problem na pół przy każdym kroku Wyszukiwanie binarne w uporządkowanej tablicy
\(O(n)\) Liniowa Czas rośnie wprost proporcjonalnie do ilości danych wejściowych Iteracja po wszystkich elementach listy
\(O(n^2)\) Kwadratowa Czas rośnie wykładniczo do ilości danych wejściowych Zagnieżdżone pętle

Przykład

Python

liczby = [1, 5, 2, 8, 3, 9, 4, 7, 6]
suma = 0

for liczba in liczby:
  suma = suma + liczba
print(suma)
#> 45

R

liczby = c(1, 5, 2, 8, 3, 9, 4, 7, 6)
suma = 0

for (liczba in liczby) {
  suma = suma + liczba
}
print(suma)
#> 45


Jaka jest złożoność czasowa powyższego algorytmu?

Algorytm geoprzestrzenny

Algorytm geoprzestrzenny

Algorytm geoprzestrzenny to procedura obliczeniowa służąca do przetwarzania i analizowania danych geoprzestrzennych (tj. w kontekście przestrzennym).

Są one przede wszystkim wykorzystywane w systemach informacji geograficznej do między innymi:

  • analizy danych teledetekcyjnych,
  • monitorowania środowiska,
  • logistyki i nawigacji,
  • planowania przestrzennego.

Przykłady algorytmów geoprzestrzennych

  • Algorytmy indeksowania przestrzennego:
    • Drzewo czwórkowe (quadtree).
    • R-drzewo (R-tree).
  • Algorytmy interpolacji przestrzennej:
    • Odwrotne ważenie odległością (Inverse Distance Weighting).
    • Kriging.
  • Algorytmy analizy sieci:
    • Algorytm Dijkstry.
    • Algorytm A* (A-star search algorithm).
  • Algorytmy geometryczne:
    • Bufor.
    • Otoczka wypukła.

Zastosowania

  • Zapytania przestrzenne (np. znalezienie punktów na określonym obszarze).
  • Operacje geometryczne (np. stworzenie buforu obiektu liniowego).
  • Transformacja współrzędnych (np. konwersja pomiędzy układami współrzędnych).
  • Interpolacja przestrzenna (np. stworzenie ciągłej powierzchni z danych punktowych).
  • Optymalizacja trasy (np. znalezienie najszybszej trasy do celu).
  • Analizy ukształtowania terenu (np. obliczenie nachylenia terenu).
  • Inne?

Technologie – języki programowania

Technologie – oprogramowanie

QGIS

Saga GIS

Grass GIS

QGIS

328 algorytmów (narzędzi) w 26 kategoriach:

  • Kafle 3D,
  • Kartografia,
  • Bazy danych,
  • Narzędzia plików,
  • GPS,
  • Interpolacja,
  • Narzędzia warstw,
  • Mesh,
  • Narzędzia modelera,
  • Analiza sieci,
  • Wykresy,
  • Przetwarzanie chmury punktów (3 moduły),
  • Przetwarzanie rastrów (4 moduły),
  • Przetwarzanie wektorów (8 modułów).

DOKUMENTACJA

Saga GIS

802 algorytmów (narzędzi) w 16 kategoriach:

  • Klimat i pogoda,
  • Różne,
  • Raster (grid),
  • Raster wielokanałowy (grid collection),
  • Przetwarzanie obrazów,
  • Import/Eksport danych,
  • Projekcje,
  • Raportowanie,
  • Wektor (shapes),
  • Symulacje,
  • Analiza przestrzenna i geostatystyka,
  • Nieregularna sieć trójkątów (TIN),
  • Dane tabelaryczne,
  • Analiza terenu,
  • Narzędzia (tool chains),
  • Wizualizacje.

DOKUMENTACJA

Grass GIS

444 algorytmów (narzędzi) w 10 kategoriach:

  • Wizualizacja,
  • Ogólne,
  • Przetwarzanie rastrów,
  • Przetwarzanie rastrów 3D,
  • Przetwarzanie obrazów,
  • Przetwarzanie wektorów,
  • Bazy danych,
  • Przetwarzanie czasowe,
  • Kartografia,
  • Różne.

DOKUMENTACJA

Geointerfejs

Geointerfejs

Interfejsy definiują sposób, w jaki różne części systemu współdziałają ze sobą, umożliwiając im komunikację i wymianę informacji.

Geointerfejs odnosi się do interfejsu, który zapewnia dostęp do danych i usług geoprzestrzennych, umożliwiając interakcje pomiędzy różnymi systemami geoprzestrzennymi za pomocą interfejsu programowania aplikacji (API).

Otwarte interfejsy umożliwiają interoperacyjność między różnymi narzędziami, nawet jeśli są napisane w innych językach programowania lub używają odmiennych struktur do reprezentacji danych.

Interfejs wiersza poleceń

Interfejs wiersza poleceń (CLI) to oparty na tekście interfejs, który umożliwia użytkownikom interakcję z systemem lub oprogramowaniem poprzez wpisywanie poleceń w konsoli.

Wykorzystanie algorytmów programów GISowych jest możliwe poprzez powłokę systemową (np. bash czy PowerShell).

Geointerfejsy w R

flowchart TD
    A[R] --> B{{<a href='https://github.com/paleolimbot/geos'>geos</a>}}
    B --> C[GEOS]
    A --> D{{<a href='https://github.com/USDAForestService/gdalraster'>gdalraster</a>}}
    D --> E[GDAL]
    A --> F{{<a href='https://github.com/stevenpawley/Rsagacmd'>Rsagacmd</a>}}
    F --> G[Saga GIS]
    A --> H{{<a href='https://github.com/OSGeo/rgrass'>rgrass</a>}}
    H --> I[Grass GIS]
    A --> J{{<a href='https://github.com/r-spatial/qgisprocess'>qgisprocess</a>}}
    J --> K[QGIS]

Przykład

Wykorzystanie QGIS CLI za pośrednictwem pakietu qgisprocess w R:

library(qgisprocess)

qgis_search_algorithms("buffer")
#>    provider_title    group                algorithm          
#>  1 GDAL              Vector geoprocessing gdal:buffervectors
#>  2 GRASS             Vector (v.*)         grass7:v.buffer   
#>  3 QGIS (native c++) Vector geometry      native:buffer     

qgis_run_algorithm(
  "native:buffer",
  INPUT = "punkt.gpkg",
  OUTPUT = "bufor.gpkg",
  DISTANCE = 100
)
#> Geometry set for 1 feature 
#> Geometry type: POLYGON
#> Dimension:     XY
#> Bounding box:  xmin: 411648 ymin: 5084491 xmax: 411668 ymax: 5084511
#> Projected CRS: NAD83 / UTM zone 20N
#> POLYGON ((411668 5084501, 411668 5084498, 4...

GDAL

Od wersji 3.11 dostępne są algorytmy geoprzestrzenne umożliwiające przetwarzanie danych rastrowych (47 algorytmów) oraz wektorowych (29 algorytmów). Przykładowo:

  • algebra rastrów,
  • reklasyfikacja wartości rastrów,
  • statystyki strefowe,
  • generowanie poziomic,
  • uproszczenie geometrii,
  • transformacja układów przestrzennych.

DOKUMENTACJA